package leetcode_周赛._2023._12;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 第 377 场周赛
 * AC_1
 *
 * @author yezh
 * @date 2023/12/24 19:11
 */
public class _24 {

    /**
     * 移除栅栏得到的正方形田地的最大面积
     * 算法：枚举
     */
    public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        Set<Integer> hSet = getSub(hFences, m), vSet = getSub(vFences, n);
        int ans = -1;
        for (Integer h : hSet) if (vSet.contains(h)) ans = Math.max(ans, h);
        return ans > 0 ? (int) ((long) ans * ans % 1_000_000_007) : -1;
    }

    Set<Integer> getSub(int[] fences, int max) {
        int n = fences.length + 2;
        fences = Arrays.copyOf(fences, n);
        fences[n - 2] = 1;
        fences[n - 1] = max;
        Arrays.sort(fences);
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) set.add(fences[j] - fences[i]);
        return set;
    }

}
